# 题目：把一个数组中最开始的若干个元素搬到数组的末尾，称之为数组的旋转。
# 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素


# 由于时递增的，所以可以使用二分来加速寻找过程

import typing


def min(ls):
    if len(ls) < 1:
        return None

    index1 = 0
    index2 = len(ls) - 1

    mid = index1

    while (ls[index2] <= ls[index1]):

        if index2 - index1 == 1:
            mid = index2
            break
        mid = (index2 + index1) // 2
        if ls[index1] == ls[mid] and ls[mid] == ls[index2]:
            return mininorder(ls,index1, index2)

        if ls[mid] >= ls[index1]:
            # 如果大于ls[index1]说明mis指针对应元素还在第一段中
            index1 = mid
        elif ls[mid] <= ls[index2]:
            index2 = mid

    return ls[mid]

def mininorder(ls, index1, index2):

    res = ls[index1]
    i = index1+1
    for i in range(index1, index2+1):
        if res > ls[i]:
            res = ls[i]
    return res

if __name__ == "__main__":

    ls = [3,4,5,1,2]
    print( min(ls))